Fibonacci number [Recursion, Bottom-Up, Top-Down, Matrix, Math, Climbing Stairs]¶
Time: O(LogN); Space: O(1); easy
The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is, * F(0) = 0, F(1) = 1 * F(N) = F(N - 1) + F(N - 2), for N > 1.
Given N, calculate F(N).
Example 1:
Input: N = 2
Output: 1
Explanation:
F(2) = F(1) + F(0) = 1 + 0 = 1.
Example 2:
Input: N = 3
Output: 2
Explanation:
F(3) = F(2) + F(1) = 1 + 1 = 2.
Example 3:
Input: N = 4
Output: 3
Explanation:
F(4) = F(3) + F(2) = 2 + 1 = 3.
Constraints:
0 ≤ N ≤ 30
1. Recursion [O(2^N), O(N)]¶
Intuition
Use recursion to compute the Fibonacci number of a given integer.
Figure 1. An example tree representing what fib(5) would look like
Algorithm
Check if the provided input value, N, is less than or equal to 1. If true, return N.
Otherwise, the function fib(int N) calls itself, with the result of the 2 previous numbers being added to each other, passed in as the argument. This is derived directly from the recurrence relation: F_{n} = F_{n-1} + F_{n-2}
Do this until all numbers have been computed, then return the resulting answer.
[7]:
class Solution1(object):
def fib(self, N: int) -> int:
if N <= 1:
return N
return self.fib(N-1) + self.fib(N-2)
[8]:
s = Solution1()
N = 2
assert s.fib(N) == 1
N = 3
assert s.fib(N) == 2
N = 4
assert s.fib(N) == 3
2. Bottom-Up using Memoization [O(N), O(N)]¶
Intuition
Improve upon the recursive option by using iteration, still solving for all of the sub-problems and returning the answer for N, using already computed Fibonacci values. In using a bottom-up approach, we can iteratively compute and store the values, only returning once we reach the result.
Algorithm
If N is less than or equal to 1, return N Otherwise, iterate through N, storing each computed answer in an array along the way. Use this array as a reference to the 2 previous numbers to calculate the current Fibonacci number. Once we’ve reached the last number, return it’s Fibonacci number.
[9]:
class Solution2(object):
def fib(self, N: int) -> int:
if N <= 1:
return N
return self.memoize(N)
def memoize(self, N: int) -> {}:
cache = {0: 0, 1: 1}
# Since range is exclusive and we want to include N, we need to put N+1.
for i in range(2, N+1):
cache[i] = cache[i-1] + cache[i-2]
return cache[N]
[10]:
s = Solution2()
N = 2
assert s.fib(N) == 1
N = 3
assert s.fib(N) == 2
N = 4
assert s.fib(N) == 3
3. Top-Down using Memoization [O(N), O(N)]¶
Intuition
Solve for all of the sub-problems, use memoization to store the pre-computed answers, then return the answer for N. We will leverage recursion, but in a smarter way by not repeating the work to calculate existing values.
Algorithm
Check if N <= 1. If it is, return N. Call and return memoize(N) If N exists in the map, return the cached value for N Otherwise set the value of N, in our mapping, to the value of memoize(N-1) + memoize(N-2)
[12]:
class Solution3(object):
def fib(self, N: int) -> int:
if N <= 1:
return N
self.cache = {0: 0, 1: 1}
return self.memoize(N)
def memoize(self, N: int) -> {}:
if N in self.cache.keys():
return self.cache[N]
self.cache[N] = self.memoize(N-1) + self.memoize(N-2)
return self.memoize(N)
[13]:
s = Solution3()
N = 2
assert s.fib(N) == 1
N = 3
assert s.fib(N) == 2
N = 4
assert s.fib(N) == 3
4. Iterative Top-Down [O(N), O(1)]¶
Intuition
Let’s get rid of the need to use all of that space and instead use the minimum amount of space required. We can achieve O(1)O(1) space complexity by only storing the value of the two previous numbers and updating them as we iterate to N.
Algorithm
Check if N <= 1, if it is then we should return N.
Check if N == 2, if it is then we should return 1 since N is 2 and fib(2-1) + fib(2-2) equals 1 + 0 = 1.
To use an iterative approach, we need at least 3 variables to store each state fib(N), fib(N-1) and fib(N-2).
Preset the initial values:
Initialize current with 0.
Initialize prev1 with 1, since this will represent fib(N-1) when computing the current value.
Initialize prev2 with 1, since this will represent fib(N-2) when computing the current value.
Iterate, incrementally by 1, all the way up to and including N. Starting at 3, since 0, 1 and 2 are pre-computed.
Set the current value to fib(N-1) + fib(N-2) because that is the value we are currently computing.
Set the prev2 value to fib(N-1).
Set the prev1 value to current_value.
When we reach N+1, we will exit the loop and return the previously set current value.
[14]:
class Solution4(object):
def fib(self, N: int) -> int:
if (N <= 1):
return N
if (N == 2):
return 1
current = 0
prev1 = 1
prev2 = 1
# Since range is exclusive and we want to include N, we need to put N+1.
for i in range(3, N+1):
current = prev1 + prev2
prev2 = prev1
prev1 = current
return current
[15]:
s = Solution4()
N = 2
assert s.fib(N) == 1
N = 3
assert s.fib(N) == 2
N = 4
assert s.fib(N) == 3
5. Matrix Exponentiation [O(logN), O(logN)]¶
Intuition
Use Matrix Exponentiation to get the Fibonacci number from the element at (0, 0) in the resultant matrix.
In order to do this we can rely on the matrix equation for the Fibonacci sequence, to find the Nth Fibonacci number:
^{n}=begin{pmatrix} : F_{(n+1)};;:F_{(n)}\ : F_{(n)};;:F_{(n-1)} \end{pmatrix}
Algorithm
Check if N is less than or equal to 1. If it is, return N.
Use a recursive function, matrixPower, to calculate the power of a given matrix A. The power will be N-1, where N is the Nth Fibonacci number.
The matrixPower function will be performed for N/2 of the Fibonacci numbers.
Within matrixPower, call the multiply function to multiply 2 matrices.
Once we finish doing the calculations, return A[0][0] to get the Nth Fibonacci number.
[16]:
class Solution5(object):
def fib(self, N: int) -> int:
if (N <= 1):
return N
A = [[1, 1], [1, 0]]
self.matrix_power(A, N-1)
return A[0][0]
def matrix_power(self, A: list, N: int):
if (N <= 1):
return A
self.matrix_power(A, N//2)
self.multiply(A, A)
B = [[1, 1], [1, 0]]
if (N%2 != 0):
self.multiply(A, B)
def multiply(self, A: list, B: list):
x = A[0][0] * B[0][0] + A[0][1] * B[1][0]
y = A[0][0] * B[0][1] + A[0][1] * B[1][1]
z = A[1][0] * B[0][0] + A[1][1] * B[1][0]
w = A[1][0] * B[0][1] + A[1][1] * B[1][1]
A[0][0] = x
A[0][1] = y
A[1][0] = z
A[1][1] = w
[17]:
s = Solution5()
N = 2
assert s.fib(N) == 1
N = 3
assert s.fib(N) == 2
N = 4
assert s.fib(N) == 3
6. Math [O(1), O(1)]¶
Intuition
Using the golden ratio, a.k.a Binet’s forumula: \varphi `= :nbsphinx-math:frac{1 + sqrt{5}}{2}` \approx 1.6180339887….φ= 2 1+ 5
Here’s a link to find out more about how the Fibonacci sequence and the golden ratio work.
We can derive the most efficient solution to this problem using only constant time and constant space!
Algorithm
Use the golden ratio formula to calculate the Nth Fibonacci number.
[18]:
class Solution6(object):
def fib(self, N):
golden_ratio = (1 + 5 ** 0.5) / 2
return int((golden_ratio ** N + 1) / 5 ** 0.5)
[19]:
s = Solution6()
N = 2
assert s.fib(N) == 1
N = 3
assert s.fib(N) == 2
N = 4
assert s.fib(N) == 3
7. Climbing Stairs [O(LogN), O(1)]¶
[26]:
class Solution7(object):
"""
Time: O(LogN)
Space: O(1)
"""
def fib(self, N):
"""
:type N: int
:rtype: int
"""
def identity(size):
size = range(size)
return [[(i == j) * 1 for i in size] for j in size]
def matrix_exp(m, pow):
assert pow >= 0 and int(pow) == pow, "Only non-negative, integer powers allowed"
accumulator = identity(len(m))
for i in range(pow):
accumulator = matrix_mult(accumulator, m)
return accumulator
def matrix_mult(m1, m2):
return [[sum(a * b for a, b in zip(m1_row, m2_col)) for m2_col in zip(*m2)] for m1_row in m1]
def print_table(data):
for row in data:
print(' '.join('%-5s' % ('%s' % cell) for cell in row))
T = [[1, 1],
[1, 0]]
return matrix_mult([[1, 0]], matrix_exp(T, N))[0][1]
[27]:
s = Solution7()
N = 2
assert s.fib(N) == 1
N = 3
assert s.fib(N) == 2
N = 4
assert s.fib(N) == 3
8. Iterative¶
[30]:
class Solution8(object):
def fib(self, N):
"""
:type N: int
:rtype: int
"""
prev, current = 0, 1
for i in range(N):
prev, current = current, prev + current
return prev
[31]:
s = Solution8()
N = 2
assert s.fib(N) == 1
N = 3
assert s.fib(N) == 2
N = 4
assert s.fib(N) == 3